#include "ExternalSorter.h"
#include <algorithm>
#include <windows.h>
#include <assert.h>
#include <set>

#pragma once

using namespace std;

static const int chunkSize = 1000 * 1000 * 10; // 40Mb of int's

static string newTempFile()
{
	char szTempFileName[MAX_PATH];
	UINT ret = GetTempFileNameA(".", "sort", 0, szTempFileName);
	assert(ret != 0);
	return szTempFileName;
}

void ExternalSorter::Sort(const string& outputFile)
{
	ifstream input(inputFile, ios_base::binary);
	assert(!input.bad());

	vector<string> tempFiles;
	
	vector<int> chunkBuffer;
	chunkBuffer.reserve(chunkSize);

	while (getChunk(input, chunkBuffer)) {
		sort(chunkBuffer.begin(), chunkBuffer.end());
		string chunkFileName = newTempFile();
		writeChunk(chunkFileName, chunkBuffer);
		chunkBuffer.clear();
		tempFiles.push_back(chunkFileName);
	}
	sortedMerge(tempFiles, outputFile);
	for (size_t i = 0; i < tempFiles.size(); i++) {
		BOOL ret = DeleteFileA(tempFiles[i].c_str());
		assert(ret != 0);
	}
}

bool ExternalSorter::getChunk(ifstream& input, vector<int>& chunkBuffer) const
{
	for (int i = 0; i < chunkSize; i++) {
		int value = 0;
		if (input.read((char*)(&value), sizeof(value))) {
			chunkBuffer.push_back(value);
		} else {
			return false;
		}
	}
	return true;
}

void ExternalSorter::writeChunk(const string& chunkFileName, vector<int>& chunkBuffer) const
{
	ofstream output(chunkFileName, ios_base::binary);
	assert(!output.bad());
	for (size_t i = 0; i < chunkBuffer.size(); i++) {
		output.write((char*)(&chunkBuffer[i]), sizeof(int));
	}
}

void ExternalSorter::sortedMerge(const vector<string>& tempFiles, const string& outputFile)
{
	vector<ifstream*> files;
	for (size_t i = 0; i < tempFiles.size(); i++) {
		ifstream* file = new ifstream(tempFiles[i], ios_base::binary);
		assert(!file->bad());
		files.push_back(file);
	}
	set<ValueIndex> heap;
	for (size_t i = 0; i < files.size(); i++) {
		int value = 0;
		if (files[i]->read((char*)(&value), sizeof(value))) {
			heap.insert(make_pair(value, i));
		} else {
			delete files[i];
			files[i] = 0;
		}
	}

	ofstream output(outputFile, ios_base::binary);
	assert(!output.bad());

	while (!heap.empty()) {
		auto iterator = heap.end();
		iterator--;
		ValueIndex valueIndex = *iterator;
		heap.erase(iterator);
		int minValue = valueIndex.first;
		output.write((char*)(&minValue), sizeof(minValue));

		int chunkIndex = valueIndex.second;
		int value = 0;
		if (files[chunkIndex] != 0 && files[chunkIndex]->read((char*)(&value), sizeof(value))) {
			heap.insert(make_pair(value, chunkIndex));
		} else {
			delete files[chunkIndex];
			files[chunkIndex] = 0;
		}
	}
	for (size_t i = 0; i < files.size(); i++) {
		assert(files[i] == 0);
	}
}